Stack Safety for Free

2015/8/8

pursの知識

JSにコンパイルされる正格評価言語だということ

型クラス、

諸々の標準的なモナド

昔のpursの知識

大きな流れ

問題提起

Freeについて見ていく

普通のFreeモナド

Freeモナド変換子

Freeのstack unsafe問題について

Scalaとかにも言及する

stack safeなFreeを作ろうぜ

普通のFreeのstack safe版

Freeモナド変換子のStack safe版

Abstract

Introduction

Host言語がJSなので、その上で関数型プログラミング的な抽象化をしてもパフォーマンスが落ちてしまうことがある

code:purs(hs)

newtype Free f a = Free (Either a (f (Free f a)))

instance Functor f => Functor (Free f) where

map g fr = g <$> fr

instance Functor f => Apply (Free f) where

apply = apply

instance Functor f => Bind (Free f) where

bind = bind

instance Functor f => Applicative (Free f) where

pure = pure

instance Functor f => Monad (Free f)

resume :: ∀ f a. Free f a -> Either a (f (Free f a))

resume (Free a) = a

liftFree :: ∀ f a. (Functor f) => f a -> Free f a

liftFree = Free <<< Right <<< map pure

runFree :: ∀ f m a.

(Monad m) =>

(f (Free f a) -> m (Free f a)) -> Free f a ->

m a

runFree phi = either pure ((_ >>= runFree phi) <<< phi) <<< resume

Freeのmonad実装などは省略されているが、自明な実装をした

derivingができないので自明でも書くしかないっぽい

The free monad can be generalized to a monad transformer, where a monadmis used to track effects at each step of the computation.

FreeモナドをFreeTに一般化する方法は困難

Current attemptsto generalize stack-safe implementations of the free monad to the free monad transformer FreeT have met with difficulty.

変換可能なMonadに制限を課すことで、Freeモナドと組み合わすことが出来るようにする

In this paper, we’ll construct a stack-safe implementation of the free monad and its monad transformer, by imposing a restriction on the class of monads which can be transformed.

Computing with Free Monads

Free f aの計算は、completeかsuspension

Counter DSL的なやつをFreeを使って作ってみる

code:purs(hs)

data CounterF a

= Increment a

| Read (Int -> a)

| Reset a

instance functorCounterF :: Functor CounterF where

map f (Increment a) = Increment (f a)

map f (Read k) = Read (f <<< k)

map f (Reset a) = Reset (f a)

3つの命令を持つ

Incrementは1つinc

Readはcurrent valueを返す

Resetはcurrent valueを0にする

code:purs(hs)

type Counter = Free CounterF

increment :: Counter Unit

increment = liftFree (Increment unit)

read :: Counter Int

read = liftFree (Read identity)

reset :: Counter Unit

reset = liftFree (Reset unit)

readAndReset :: Counter Int

readAndReset = do

current <- read

reset

pure current

他の例としては、Affと組み合わせてremote server上の値を非同期で更新するとか、Effでlogを吐くとか

This is the powerof working with free monads we have completely separated the interpretation of our computations from the syntax that describes them.

構文と解釈が完全に分離している、分離できる

Free Monad Transformers

code:purs(hs)

newtype FreeT f m a = FreeT (m (Either a (f (FreeT f m a))))

instance (Functor f, Monad m) => Functor (FreeT f m) where

map f = FreeT <<< map (bimap f (map (map f))) <<< resumeT

instance (Functor f, Monad m) => Apply (FreeT f m) where

apply = ap

instance (Functor f, Monad m) => Bind (FreeT f m) where

bind (FreeT a) f = FreeT (a >>= go)

where

go (Left a) = resumeT (f a)

go (Right fs) = pure (Right (map (_ >>= f) fs))

instance (Functor f, Monad m) => Applicative (FreeT f m) where

pure = FreeT <<< pure <<< Left

instance (Functor f, Monad m) => Monad (FreeT f m)

instance (Functor f) => MonadTrans (FreeT f) where

lift = FreeT <<< map Left

resumeT :: ∀ f m a. FreeT f m a -> m (Either a (f (FreeT f m a)))

resumeT (FreeT a) = a

liftFreeT :: ∀ f m a. Functor f => Monad m => f a -> FreeT f m a

liftFreeT = FreeT <<< pure <<< Right <<< map pure

runFreeT :: ∀ f m a.

(Monad m) =>

(f (FreeT f m a) -> m (FreeT f m a)) -> FreeT f m a ->

m a

runFreeT phi = either pure ((_ >>= runFreeT phi) <<< phi) <=< resumeT

code:purs(hs)

type CounterT = FreeT CounterF

incrementT :: ∀ m. (Monad m) => CounterT m Unit

incrementT = liftFreeT (Increment unit)

readT :: ∀ m. (Monad m) => CounterT m Int

readT = liftFreeT (Read identity)

resetT :: ∀ m. (Monad m) => CounterT m Unit

resetT = liftFreeT (Reset unit)

Deffering Monadic Binds

<Bjarnason> describes how to defer monadic binds in the free monad, by capturing binds as a data structure.

そのデータ構造をcaputureすることで、bindを延期できる

末尾再帰関数を使用して、Freeを解釈し、延期したbindの構造を折りたたむ

そうすることで、深い再帰をサポートするFree monadの実装ができる

ただし、この方法には制限がある

base monadとして使用できるmは、stack safeである必要がある

「任意のモナドをtargetに取れる」と言っている割に制限があるということか？

code:purs(hs)

data GosubF f a b = GosubF (Unit -> Free f b) (b -> Free f a)

data Free f a

= Free (Either a (f (Free f a)))

| Gosub (Exists (GosubF f a))

Tail Recursive Monads

Scalaのやり方では制限があるので、なんとかしよう、という流れ

これはちゃんと末尾呼び出しの除去される

code:purs(hs)

pow :: Int -> Int -> Int

pow n p = go (Tuple 1 p)

where

go (Tuple acc 0) = acc

go (Tuple acc p) = go (Tuple (acc * n) (p - 1))

しかし、Monadを使った再帰をすると最適化されない

code:purs(hs)

powWriter :: Int -> Int -> Writer Product Unit

powWriter n = go

where

go 0 = pure unit

go m = do

tell n

go $ m -1

末尾再帰関数を一般化する

末尾再帰は、「終了」もしくは「自分自身の呼び出し」にパターン化できるのでこれを一般化した関数を定義できる

code:purs(hs)

tailRec :: ∀ a b. (a -> Either a b) -> a -> b

tailRec f a = go (f a)

where

go (Left a) = go (f a)

go (Right b) = b

Left側は、「値」ではなく、「関数」を返している

tailRecを使って、powを書き直すr

code:purs(hs)

pow :: Int -> Int -> Int

pow n p = tailRec go (Tuple 1 p)

where

go :: Tuple Int Int -> Either (Tuple Int Int) Int

go (Tuple acc 0) = Right acc

go (Tuple acc p) = Left $ Tuple (acc * n) (p - 1)

code:purs(hs)

class Monad m <= MonadRec m where

tailRecM :: forall a b. (a -> m (Either a b)) -> a -> m b

構造としてはほぼ同じ

data Step a b = Loop a | Done b

MonadRecは任意のMonadに対して定義できることがわかる

MonadRecはいろいろinstanceが用意されているので便利

StateT, WriterT, ExcpeTなどにMonadRecは使われている

組み合わせたら色々出来るよ、と言っている

Interpreting Free Monads Safely

必要に応じて遅延もなどのbindをunpackingする

復習すると

code:purs(hs)

-- ただのFree型に対する実装

resume :: ∀ f a. Free f a -> Either a (f (Free f a))

resume (Free a) = a

-- FreeTに対する実装

resumeT :: ∀ f m a. FreeT f m a -> m (Either a (f (FreeT f m a)))

resumeT (FreeT a) = a

-- 末尾再帰にしたstack safeな実装

resume

:: forall f a

. Functor f

=> Free f a

-> Either (f (Free f a)) a

resume = ..

code:purs(hs)

tailRecM' f a = f a >>= go

where

go (Left a) = f a >>= go

go (Right b) = pure b

resume

:: forall f a

. Functor f

=> Free f a

-> Either (f (Free f a)) a

runFree :: ∀ f m a.

Functor f => Monad m =>

(f (Free f a) -> m (Free f a)) -> Free f a -> m a

runFree phi = tailRecM \m ->

case resume m of

Left fs -> map Left (phi fs)

Right a -> pure $ Right a

Here, the MonadRec instance is used to define a tail-recursive function whichunrolls the data structure of monadic binds, one step at a time.

MonadRecインスタンスは、monadic bindのデータ構造を一度に1ステップずつ展開する末尾再帰関数を定義するために使用される

これによって、有効なtarget monadの範囲を拡大できた

Stack-Safe Free Monad Transformers

Stack SafeなFreeを作れたので、次はそれのモナド変換子を作ろう

code:purs(hs)

data GosubF f m a b = GosubF (Unit -> FreeT f m a) (a -> FreeT f m b)

data FreeT f m a

= FreeT (Unit -> m (Either a (f (FreeT f m a))))

| Gosub (Exists (GosubF f m a))

FunctorやMonadのinstanceは、FreeからFreeTまで上手く一般化されている

問題はtarget monad mでFreeTの計算をどう実行するか

code:prus(hs)

resume ::

∀ f m a.Functor f => MonadRec m =>

FreeT f m a ->m (Either a (f (FreeT f m a)))

resume = tailRecM go

where

go :: FreeT f m a -> m (Either (FreeT f m a) (Either a (f (FreeT f m a))))

go (FreeT f) = map Right (f unit)

go (Gosub e) = runExists (\(GosubF m f) ->

case m unit of

FreeT m -> do

e <- m unit

case e of

Left a -> pure (Left (f a))

Right fc -> pure (Right (Right (map (\h -> h >>= f) fc)))

Gosub e1 -> runExists (\(GosubF m1 f1) ->

pure (Left (bind (m1 unit) (\z -> f1 z >>= f)))) e1) e

runFreeT :: ∀ f m a.

Functor f => MonadRec m =>

(f (FreeT f m a) -> m (FreeT f m a)) ->FreeT f m a ->m a

runFreeT interp = tailRecM (go <=< resume)

where

go :: Either a (f (FreeT f m a)) -> m (Either (FreeT f m a) a)

go (Left a) = pure (Right a)

go (Right fc) = do

c <- interp fc

pure (Left c)

MonadRecのinstanceであるmonadならstack safeになった

Stack Safety for Free

code:purs(hs)

newtype Identity a = Identity a

runIdentity :: forall a. Identity a -> a

runIdentity (Identity a) = a

type SafeT = FreeT Identity

runSafeT :: forall m a. (MonadRec m) => SafeT m a -> m a

runSafeT = runFreeT (pure <<< runIdentity)

Identityに対してFreeTを使って、Freeを得ている

mがMonadRecなら、

runSafeTが解釈を与えてくれる

stack over flowを心配せずに、入れ子になっているmonadを使用できる

入れ子は、モナド変換子の文脈での入れ子

code:purs(hs)

import Control.Monad.Free.Trans (FreeT, runFreeT)

import Control.Monad.Rec.Class (class MonadRec)

import Data.Identity (Identity(..))

import Effect (Effect)

import Effect.Class (liftEffect)

import Effect.Class.Console (log)

runIdentity :: forall a. Identity a -> a

runIdentity (Identity a) = a

type SafeT = FreeT Identity

runSafeT :: forall m a. (MonadRec m) => SafeT m a -> m a

runSafeT = runFreeT (pure <<< runIdentity)

main :: Effect Unit

main = go 100000

where

go :: Int -> Effect Unit

go n | n <= 0 = pure unit

go n = do

log $ show n

go (n - 2)

go (n - 1)

main' :: Effect Unit

main' = runSafeT $ go 100000

where

go :: Int -> SafeT Effect Unit

go n | n <= 0 = pure unit

go n = do

liftEffect (log $ show n)

go (n - 2)

go (n - 1)

Application: Coroutines

Free monad transformers can be used to construct models ofcoroutines, by usingthe base functor to specify the operations which can take place when a coroutinesuspends.

base functorが、「コルーチンの中断時に実行できる操作」を表す

サスペンションでの単一の操作をサポートするベースファンクタEmit

code:purs(hs)

data Emit o a = Emit o a

instance Functor (Emit o) where

map f (Emit o a) = Emit o (f a)

値のみを生成するProducer型

Freeで囲んでいるのでMonadになる

code:purs(hs)

type Producer o = FreeT (Emit o)

emitは、単一の出力値を出力

code:purs(hs)

emit :: forall o m. (Monad m) => o -> FreeT (Emit o) m Unit

emit o = liftFreeT (Emit o unit)

code:purs(hs)

producer :: ∀ m. Monad m => MonadEffect m => Producer String m Unit

producer = forever do

liftEffect $ log "Emitting a value..."

emit "Hello World"

code:purs(hs)

data Await i a = Await (i -> a)

instance Functor (Await i) where

map f (Await k) = Await (f <<< k)

type Consumer i = FreeT (Await i)

await :: ∀ i m. Monad m => Consumer i m i

await = liftFreeT (Await identity)

consumer :: ∀ m. Monad m => MonadEffect m => FreeT (Await String) m Unit

consumer = forever do

s <- await

liftEffect $ log s

purescript-coroutines

ちょっと飛ばした

Application: List Monad Transformer

ListTを使うことで、副作用のある非決定的計算を表すことが出来る

これはFree関係ない一般的なListTの話

しかし、stack safeなListTを構築する方法は自明でない

Freeと組み合わせてListTを定義すればいいじゃない

code:purs(hs)

data ListF a r t = Nil r | Cons a t

newtype ListT m a r = ListT (m (ListF a r (ListT m a r)))

Procedureを使ってListTを再定義

code:purs(hs)

newtype ListT m a = ListT (Producer a m Unit)

ちょっと飛ばした

Application: Lifting Control Operators